Performance Models for the Spike Banded Linear System Solver.

Functional characterization and topological modularity of molecular interaction networks.

Special issue on Parallel Matrix Algorithms and Applications.

Weighted Matrix Ordering and Parallel Banded Preconditioners for Iterative Linear System Solvers.

Contemporary Computing %2D Second International Conference

Load Balancing for Parallel Optimization Techniques.

Load Balancing for Parallel Optimization Techniques.



Functional coherence in domain interaction networks.

Scalable Data Collection in Sensor Networks.

Annotating Pathways of Interaction Networks.
Integrating molecular interaction data with existing knowledge of molecular function reveals mechanisms that underly cellular organization. We present NARADA, a software tool that implements a comprehensive analysis suite for functional annotation of pathways. NARADA takes as input a species-specific molecular interaction network and annotation of biomolecules in the network and provides the user with a set of pathways composed of functional attributes, which may be thought of pathway templates in the functional annotation space that recur in various contexts (different groups of specific molecules with similar functional annotation patterns) in the molecular interaction network. NARADA has its underpinnings in formal statistical measures of significance, and algorithmic bases for performance. Comprehensive evaluation on the E. coli transcriptional regulation and proteinprotein interaction data demonstrate NARADA’s ability to detect known, as well as novel pathways. 1.
PHALANX a graph%2Dtheoretic framework for test case prioritization.



Semantic indexing in structured peer%2Dto%2Dpeer networks.

Macroprogramming heterogeneous sensor networks using cosmos.
In this paper, we present COSMOS, a novel architecture for macroprogramming heterogeneous sensor network systems. Macroprogramming specifies aggregate system behavior, as opposed to device-specific programs that code distributed behavior using explicit messaging. COSMOS is comprised of a macroprogramming language, mPL, and an operating system, mOS. mPL macroprograms are statically verifiable compositions of reusable user-specified, or system supported functional components. The mOS node/network operating system provides component management and a lean execution environment for mPL programs in heterogeneous resource-constrained sensor networks. It provides runtime application instantiation, with over-the-air reprogramming of the network. COSMOS facilitates composition of complex real-world applications that are robust, scalable and adaptive in dynamic data-driven sensor network environments. An important and novel aspect of COSMOS is the ability to easily extend its component basis library to add rich macroprogramming abstractions to mPL, tailored to domain and resource constraints, without modifications to the OS. Applications built on COSMOS are currently in use at the Bowen Labs for Structural Engineering, in Purdue University, for high-fidelity structural monitoring. We present a detailed description of the COSMOS architecture, its various components, and a comprehensive experimental evaluation using macro- and micro- benchmarks to demonstrate performance characteristics of COSMOS.
Path%2DSensitive Inference of Function Precedence Protocols.
Function precedence protocols define ordering relations among function calls in a program. In some instances, precedence protocols are well-understood (e.g., a call to pthread mutex init must always be present on all program paths before a call to pthread mutex lock). Oftentimes, however, these protocols are neither welldocumented, nor easily derived. As a result, protocol violations can lead to subtle errors that are difficult to identify and correct. In this paper, we present CHRONICLER, a tool that applies scalable inter-procedural path-sensitive static analysis to automatically infer accurate function precedence protocols. CHRONICLER computes precedence relations based on a program’s control-flow structure, integrates these relations into a repository, and analyzes them using sequence mining techniques to generate a collection of feasible precedence protocols. Deviations from these protocols found in the program are tagged as violations, and represent potential sources of bugs. We demonstrate CHRONICLER’s effectiveness by deriving protocols for a collection of benchmarks ranging in size from 66K to 2M lines of code. Our results not only confirm the existence of bugs in these programs due to precedence protocol violations, but also highlight the importance of path sensitivity on accuracy and scalability. 
Functional annotation of regulatory pathways.
Motivation: Standardized annotations of biomolecules in interaction networks (e.g., Gene Ontology) provide comprehensive understanding of the function of individual molecules. Extending such annotations to pathways is a critical component of functional characterization of cellular signaling at the systems level. Results: We propose a framework for projecting gene regulatory networks onto the space of functional attributes using multigraph models, with the objective of deriving statistically significant pathway annotations. We first demonstrate that annotations of pairwise interactions do not generalize to indirect relationships between processes. Motivated by this result, we formalize the problem of identifying statistically over-represented pathways of functional attributes. We establish the hardness of this problem by demonstrating the non-monotonicity of common statistical significance measures. We propose a statistical model that emphasizes the modularity of a pathway, evaluating its significance based on the coupling of its building blocks. We complement the statistical model by an efficient algorithm and software, NARADA, for computing significant pathways in large regulatory networks. Comprehensive results from our methods applied to the E. coli transcription network demonstrate that our approach is effective in identifying known, as well as novel biological pathway annotations. Availability: NARADA is implemented in Java and is available at
Building Verifiable Sensing Applications Through Temporal Logic Specification.

Building Verifiable Sensing Applications Through Temporal Logic Specification.

Static specification inference using predicate mining.

Randomized leader election.
We investigate the duration of an elimination process for identifying a winner by coin tossing, or, equivalently, the height of a random incomplete trie. Applications of the process include the election of a leader in a computer network. Using direct probabilistic arguments we obtain exact expressions for the discrete distribution and the moments of the height. Elementary approximation techniques then yield asymptotics for the distribution. We show that no limiting distribution exists, as the asymptotic expressions exhibit periodic fluctuations. In many similar problems associated with digital trees, no such exact expressions can be derived. We therefore outline a powerful general approach, based on the analytic techniques of Mellin transforms, Poissonization, and de-Poissonization, from which distributional asymptotics for the height can also be derived. In fact, it was this complex variables approach that led to our original discovery of the exact distribution. Complex analysis metho...
Randomized Protocols for Duplicate Elimination in Peer%2Dto%2DPeer Storage Systems.
Distributed peer-to-peer storage systems rely on voluntary participation of peers to effectively manage a storage pool. Files are generally replicated in several sites to provide acceptable levels of availability. If disk space on these peers is not carefully monitored and provisioned, the system may not be able to provide availability for certain files. In particular, identification and elimination of redundant data are important problems that may arise in long-lived systems. Scalability and availability are competing goals in these networks: scalability concerns would dictate aggressive elimination of replicas, while availability considerations would argue conversely. In this paper, we provide a novel and efficient solution that addresses both these goals with respect to management of redundant data. Specifically, we address the problem of duplicate elimination in the context of systems connected over an unstructured peerto-peer network in which there is no a priori binding between an object and its location. We propose a new randomized protocol to solve this problem in a scalable and decentralized fashion that does not compromise availability requirements of the application. Performance results using both large-scale simulations, and a prototype built on PlanetLab, demonstrate that the protocols provide high probabilistic guarantees of success, while incurring minimal administrative overheads. 1.
Assessing Significance of Connectivity and Conservation in Protein Interaction Networks.
Computational and comparative analysis of protein-protein interaction (PPI) networks enable understanding of the modular organization of the cell through identification of functional modules and protein complexes. These analysis techniques generally rely on topological features such as connectedness, based on the premise that functionally related proteins are likely to interact densely and that these interactions follow similar evolutionary trajectories. Significant recent work in our lab, and in other labs has focused on efficient algorithms for identification of modules and their conservation. Application of these methods to a variety of networks has yielded novel biological insights. In spite of algorithmic advances, development of a comprehensive infrastructure for interaction databases is in relative infancy compared to corresponding sequence analysis tools such as BLAST and CLUSTAL. One critical component of this infrastructure is a measure of the statistical significance of a match or a dense subcomponent. Corresponding sequence-based measures such as E-values are key components of sequence matching tools. In the absence of an analytical measure, conventional methods rely on computer simulations based on ad-hoc models for quantifying significance. This paper presents the first such effort, to the best of our knowledge, aimed at analytically quantifying statistical significance
Sieve A Tool for Automatically Detecting Variations Across Program Versions.
Revisions are an essential cllaracteristic of large-scale software development. Software systems often undergo many revisions during their lifetime because new features are added, bugs repaired, abstractions simplified and refactored, and performance improved. When a revision: even a minor one: does occur: the changes it induces must be tested to ensure that assumed invariants in the original are not violated. In order to avoid testing components that are unchanged across revisions: impact analysis is often used to identify those code blocks or functions that. are affected by a. change. In this paper, we present a new solution to this general problem that uses dynamic progranlming on inst.rumented traces of different program binaries to identify longest common subsequences in the strings generated by these traces. Our formulation not only allo\\~s 11s to perform impact analysis, but can also be used to detect the smallest set of locations within these functions where the effect of the changes actually manifest. Sieve is a tool that incorporates these ideas. Sieve is unobtrusive, requiring no programmer or compiler involvement to guide its behavior. We have tested Sieve on multiple versions of open-source C programs and find that the accuracy of impact analysis is improved by 10- 30 % compared to existing state-of-the-art implementations. hlore significantly, Sieve can identify the regions \\here the changes manifest: and discovers that lor the vast majority of impacted lunctions: the locus of change is limited to often less than three lines of code. These results lead us to conclude that Sieve can play a beneficial role in program testing and software maintenance. 1.
Trace%2DBased Memory Aliasing Across Program Versions.
Abstract. One of the major costs of software development is associated with testing and validation of successive versions of software systems. An important problem encountered in testing and validation is memory aliasing, which involves correlation of variables across program versions. This is useful to ensure that existing invariants are preserved in newer versions and to match program execution histories. Recent work in this area has focused on trace-based techniques to better isolate affected regions. A variation of this general approach considers memory operations to generate more refined impact sets. The utility of such an approach eventually relies on the ability to effectively recognize aliases. In this paper, we address the general memory aliasing problem and present a probabilistic trace-based technique for correlating memory locations across execution traces, and associated variables in program versions. Our approach is based on computing the log-odds ratio, which defines the affinity of locations based on observed patterns. As part of the aliasing process, the traces for initial test inputs are aligned without considering aliasing. From the aligned traces, the log-odds ratio of the memory locations is computed. Subsequently, aliasing is used for alignment of successive traces. Our technique can easily be extended to other applications where detecting aliasing is necessary. As a case study, we implement and use our approach in dynamic impact analysis for detecting variations across program versions. Using detailed experiments on real versions of software systems, we observe significant improvements in detection of affected regions when aliasing occurs. 1
Distributed Uniform Sampling in Unstructured Peer%2Dto%2DPeer Networks.

The Omni Macroprogramming Environment for Sensor Networks.

Assessing Significance of Connectivity and Conservation in Protein Interaction Networks.
Computational and comparative analysis of protein-protein interaction (PPI) networks enable understanding of the modular organization of the cell through identification of functional modules and protein complexes. These analysis techniques generally rely on topological features such as connectedness, based on the premise that functionally related proteins are likely to interact densely and that these interactions follow similar evolutionary trajectories. Significant recent work in our lab, and in other labs has focused on efficient algorithms for identification of modules and their conservation. Application of these methods to a variety of networks has yielded novel biological insights. In spite of algorithmic advances, development of a comprehensive infrastructure for interaction databases is in relative infancy compared to corresponding sequence analysis tools such as BLAST and CLUSTAL. One critical component of this infrastructure is a measure of the statistical significance of a match or a dense subcomponent. Corresponding sequence-based measures such as E-values are key components of sequence matching tools. In the absence of an analytical measure, conventional methods rely on computer simulations based on ad-hoc models for quantifying significance. This paper presents the first such effort, to the best of our knowledge, aimed at analytically quantifying statistical significance
Nonorthogonal decomposition of binary matrices for bounded%2Derror data compression and analysis.
This article presents the design and implementation of a software tool, PROXIMUS, for error-bounded approximation of high-dimensional binary attributed datasets based on nonorthogonal decomposition of binary matrices. This tool can be used for analyzing data arising in a variety of domains ranging from commercial to scientific applications. Using a combination of innovative algorithms, novel data structures, and efficient implementation, PROXIMUS demonstrates excellent accuracy, performance, and scalability to large datasets. We experimentally demonstrate these on diverse applications in association rule mining and DNA microarray analysis. In limited beta release, PROXIMUS currently has over 300 installations in over 10 countries.
CONQUEST A Coarse%2DGrained Algorithm for Constructing Summaries of Distributed Discrete Datasets.

Inferring functional information from domain co%2Devolution.

Locality in structured peer%2Dto%2Dpeer networks.
Distributed hash tables (DHTs), used in a number of structured peer-to-peer (P2P) systems provide efficient mechanisms for resource placement and location. A key distinguishing feature of current DHT systems, such as Chord, Pastry, CAN and Tapestry, is the way they handle locality in the underlying network. Topology-based node identifier assignment, proximity routing, and proximity neighbor selection are examples of heuristics used to minimize message delays in the underlying network. While these heuristics are sometimes effective, they all rely on a single global overlay that may install the key of a popular object at a node far from most of the nodes accessing it. Furthermore, a response to a lookup message does not contain any locality information about the nodes holding a copy of the object. We address these issues in Plethora, a novel two-level overlay P2P network. A local overlay in Plethora acts as a locality-aware cache for the global overlay, grouping nodes close together in the underlying network. Local overlays are constructed by exploiting the organization of the Internet into Autonomous Systems (ASs). We present a detailed experimental study that demonstrates performance gains in response time of up to 60 % compared to a single global Pastry overlay. We also present efficient distributed algorithms for maintaining local overlays in the presence of node arrivals and departures.
Pairwise Alignment of Protein Interaction Networks.
With an ever-increasing amount of available data on protein–protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein–protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost. Key words: protein–protein interactions, network alignment, evolutionary models. 1.
Detecting Conserved Interaction Patterns in Biological Networks.
Molecular interaction data plays an important role in understanding biological processes at a modular level by providing a framework for understanding cellular organization, functional hierarchy, and evolutionary conservation. As the quality and quantity of network and interaction data increases rapidly, the problem of effectively analyzing this data becomes significant. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm, MULE, for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique based on ortholog contraction, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable and scalable to large numbers of networks. We show, experimentally, that our algorithm can extract frequently occurring patterns in metabolic pathways and protein interaction networks from the KEGG, DIP, and BIND databases within seconds. When compared to existing approaches, our graph simplification technique can be viewed either as a pruning heuristic, or a closely related, but computationally simpler task. When used as a pruning heuristic, we show that our technique reduces effective graph sizes significantly, accelerating existing techniques by several orders of magnitude! Indeed, for most of the test cases, existing techniques could not even be applied without our pruning step. When used as a stand-alone analysis technique, MULE is shown to convey significant biological insights at near-interactive rates. The software, sample input graphs, and detailed results for comprehensive analysis of nine eukaryotic PPI networks are available at www.cs.purdue.edu/homes/koyuturk/mule. Key words: graph mining, frequent subgraph discovery, evolution, modular conservation. 1.
Unstructured peer%2Dto%2Dpeer networks for sharing processor cycles.
Motivated by the needs and success of projects such as
Redundancy and coverage detection in sensor networks.
We study the problem of detecting and eliminating redundancy in a sensor network with a view to improving energy efficiency, while preserving the network’s coverage. We also examine the impact of redundancy elimination on the related problem of coverage-boundary detection. We reduce both problems to the computation of Voronoi diagrams, prove and achieve lower bounds on the solution of these problems, and present efficient distributed algorithms for computing and maintaining solutions in cases of sensor failures or insertion of new sensors. We prove the correctness and termination properties of our distributed algorithms, and analytically characterize the time complexity and traffic generated by our algorithms. Using detailed simulations, we also quantify the impact of system parameters such as sensor density, transmission range, and failure rates on network traffic.


Search with Probabilistic Guarantees in Unstructured Peer%2Dto%2DPeer Networks.
Search is a fundamental service in peer-to-peer (P2P) networks. However, despite numerous research efforts, efficient algorithms for guaranteed location of shared content in unstructured P2P networks are yet to be devised. In this paper, we present a simple but highly effective protocol for object location that gives probabilistic guarantees of finding even rare objects independently of the network topology. The protocol relies on randomized techniques for replication of objects (or their references) and for query propagation. We prove analytically, and demonstrate experimentally, that our scheme provides high probabilistic guarantees of success, while incurring minimal overhead. We quantify the performance of our scheme in terms of network messages, probability of success, and response time. We also evaluate the robustness of our protocol in the presence of node failures (departures). Using simulation, we show that our scheme performs no worse than the best known access-frequency based protocols, without compromising access to rare objects. 1.
Randomized Protocols for Duplicate Elimination in Peer%2Dto%2DPeer Storage Systems.
Distributed peer-to-peer storage systems rely on voluntary participation of peers to effectively manage a storage pool. Files are generally replicated in several sites to provide acceptable levels of availability. If disk space on these peers is not carefully monitored and provisioned, the system may not be able to provide availability for certain files. In particular, identification and elimination of redundant data are important problems that may arise in long-lived systems. Scalability and availability are competing goals in these networks: scalability concerns would dictate aggressive elimination of replicas, while availability considerations would argue conversely. In this paper, we provide a novel and efficient solution that addresses both these goals with respect to management of redundant data. Specifically, we address the problem of duplicate elimination in the context of systems connected over an unstructured peerto-peer network in which there is no a priori binding between an object and its location. We propose a new randomized protocol to solve this problem in a scalable and decentralized fashion that does not compromise availability requirements of the application. Performance results using both large-scale simulations, and a prototype built on PlanetLab, demonstrate that the protocols provide high probabilistic guarantees of success, while incurring minimal administrative overheads. 1.
Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution.
Abstract. With ever increasing amount of available data on proteinprotein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Recent algorithms on aligning PPI networks target simplified structures such as conserved pathways to render these problems computationally tractable. However, since conserved structures that are parts of functional modules and protein complexes generally correspond to dense subnets of the network, algorithms that are able to extract conserved patterns in terms of general graphs are necessary. With this motivation, we focus here on discovering protein sets that induce subnets that are highly conserved in the interactome of a pair of species. For this purpose, we develop a framework that formally defines the pairwise local alignment problem for PPI networks, models the problem as a graph optimization problem, and presents fast algorithms for this problem. In order to capture the underlying biological processes correctly, we base our framework on duplication/divergence models that focus on understanding the evolution of PPI networks. Experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively (in terms of accuracies and computational cost). While we focus on pairwise local alignment of PPI networks in this paper, the proposed algorithm can be easily adapted to finding matches for a subnet query in a database of PPI networks. 1
Adaptive data structures for IP lookups.
The problem of efficient data structures for IP lookups has been well studied in literature. Techniques such as LC tries and Extensible Hashing are commonly used. In this paper, we address the problem of generalizing LC tries and Extensible Hashing, based on traces of past lookups, to provide performance guarantees for memory sub-optimal structures. As a specific example, if a memory-optimal (LC) trie takes 6MB and the total memory at the router is 8MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are b fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have  22 fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of O(#(d)n    log n) and a space complexity of O(n), where n is the number of nodes of the trie and d its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically O(log n).Inthiscase,#(d)=O(log    n). We demonstrate experimentally the performance and scalability of the algorithm on actual routing data. We also show that our algorithm significantly outperforms Extensible Hashing for the same amount of memory.
Level compressed DAGs for lookup tables.

Compression
We study the notion of Compressed Sensing (CS) as put forward in [14] and related work [20, 3, 4]. The basic idea behind CS is that a signal or image, unknown but supposed to be compressible by a known transform, (eg. wavelet or Fourier), can be subjected to fewer measurements than the nominal number of pixels, and yet be accurately reconstructed. The samples are nonadaptive and measure ‘random ’ linear combinations of the transform coefficients. Approximate reconstruction is obtained by solving for the transform coefficients consistent with measured data and having the smallest possible ℓ 1 norm. We perform a series of numerical experiments which validate in general terms the basic idea proposed in [14, 3, 5], in the favorable case where the transform coefficients are sparse in the strong sense that the vast majority are zero. We then consider a range of less-favorable cases, in which the object has all coefficients nonzero, but the coefficients obey an ℓ p bound, for some p ∈ (0, 1]. These experiments show that the basic inequalities behind the CS method seem to involve reasonable constants. We next consider synthetic examples modelling problems in spectroscopy and image processing, and note that reconstructions from CS are often visually “noisy ”. We post-process using translation-invariant de-noising, and find the visual appearance considerably improved. We also consider a multiscale deployment of compressed sensing, in which various scales are segregated and CS applied separately to each; this gives much better quality reconstructions than a literal deployment of the CS methodology. We also report that several workable families of ‘random ’ linear combinations all behave equivalently, including random spherical, random signs, partial Fourier and partial Hadamard. These results show that, when appropriately deployed in a favorable setting, the CS framework is able to save significantly over traditional sampling, and there are many useful extensions of the basic idea.

Biclustering Gene%2DFeature Matrices for Statistically Significant Dense Patterns.
Biclustering is an important problem that arises in diverse applications, including analysis of gene expression and drug interaction data. The problem can be formalized in various ways through different interpretation of data and associated optimization functions. We focus on the problem of finding unusually dense patterns in binary (0-1) matrices. This formulation is appropriate for analyzing experimental datasets that come from not only binary quantization of gene expression data, but also more comprehensive datasets such as gene-feature matrices that include functions of coded proteins and motifs in the coding sequence. We formalize the notion of an “unusually ” dense submatrix to evaluate the interestingness of a pattern in terms of statistical significance based on the assumption of a uniform memoryless source. We then simplify it to assess statistical significance of discovered patterns. Using statistical significance as an objective function, we formulate the problem as one of finding significant dense submatrices of a large sparse matrix. Adopting a simple iterative heuristic along with randomized initialization techniques, we derive fast algorithms for discovering binary biclusters. We conduct experiments on a binary gene-feature matrix and a quantized breast tumor gene expression matrix. Our experimental results show that the proposed method quickly discovers all interesting patterns in these datasets. 1.

Parallel Performance of Hierarchical Multipole Algorithms for Inductance Extraction.

Extended Consistent Hashing An Efficient Framework for Object Location.

Distributed and Dynamic Voronoi Overlays for Coverage Detection and Distributed Hash Tables in Ad%2DHoc Networks.

A Secure Crediting Protocol for Hybrid Cellular and Ad%2DHoc Networks.
hybrid cellular ad-hoc networks, security, routing protocols While wireless networking seems to be the way of the future, no definite architecture for large scale deployment of such networks has emerged. This can be attributed to financial reasons (a specialized infrastructure is too expensive to build) as well as to the lack of solutions that could work with an existing infrastructure or, in an ad hoc manner, without one. A viable alternative seems to be hybrid wireless networks. Such networks use the existing cellular telephony infrastructure as basis and enhance it by building ad hoc networks of traffic relayers around each cell, improving the overall throughtput and reliability of the network. These relayers are users of the network that are willing to operate as such. In this setting, both efficiency and security are vital properties. We propose SCP as an integrated solution for secure routing and crediting in hybrid networks. We describe how a secure environment can be established efficiently by financially motivating users to avoid attacks. Finally, we show that SCP imposes minimal load both in communication and computation, so that even regular cellular phones can function as relayers, without demanding infrastructure upgrades. 1
Enhancing Locality in Structured Peer%2Dto%2DPeer Networks.
Distributed hash tables (DHTs), used in a number of structured peer-to-peer (P2P) systems provide efficient mechanisms for resource placement and location. A key distinguishing feature of current DHT systems, such as Chord, Pastry, CAN and Tapestry, is the way they handle locality in the underlying network. Topology-based node identifier assignment, proximity routing, and proximity neighbor selection are examples of heuristics used to minimize message delays in the underlying network. While these heuristics are sometimes effective, they all rely on a single global overlay that may install the key of a popular object at a node far from most of the nodes accessing it. Furthermore, a response to a lookup message does not contain any locality information about the nodes holding a copy of the object. We address these issues in Plethora, a novel two-level overlay P2P network. A local overlay in Plethora acts as a locality-aware cache for the global overlay, grouping nodes close together in the underlying network. Local overlays are constructed by exploiting the organization of the Internet into Autonomous Systems (ASs). We present a detailed experimental study that demonstrates performance gains in response time of up to 60 % compared to a single global Pastry overlay. We also present efficient distributed algorithms for maintaining local overlays in the presence of node arrivals and departures.
Distributed and Dynamic Voronoi Overlays for Coverage Detection and Distributed Hash Tables in Ad%2DHoc Networks.

Impact of far%2Dfield interactions on performance of multipole%2Dbased preconditioners for sparse linear systems.

An efficient algorithm for detecting frequent subgraphs in biological networks.
With rapidly increasing amount of network and interaction data in molecular biology, the problem of effectively analyzing this data is an important one. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable. Indeed, we show experimentally that our algorithm can extract frequently occurring patterns in metabolic pathways extracted from the KEGG database within seconds. The proposed model and algorithm are applicable to a variety biological networks either directly or with minor modifications. Implementation of the proposed algorithms in the C programming language is available as open source at http://www.cs.purdue.edu/homes/koyuturk/pathway/.
Model Reduction of Large%2DScale Dynamical Systems.
Abstract. Simulation and control are two critical elements of Dynamic Data-Driven Application Systems (DDDAS). Simulation of dynamical systems such as weather phenomena, when augmented with real-time data, can yield precise forecasts. In other applications such as structural control, the presence of real-time data relating to system state can enable robust active control. In each case, there is an ever increasing need for improved accuracy, which leads to models of higher complexity. The basic motivation for system approximation is the need, in many instances, for a simplified model of a dynamical system, which captures the main features of the original complex model. This need arises from limited computational capability, accuracy of measured data, and storage capacity. The simplified model may then be used in place of the original complex model, either for simulation and prediction, oractive control. As sensor networks and embedded processors proliferate our environment, technologies for such approximations and real-time control emerge as the next major technical challenge. This paper outlines the state of the art and outstanding challenges in the development of efficient and robust methods for producing reduced order models of large state-space systems. 1
Conquest A Distributed Tool for Constructing Summaries of High%2DDimensional Discrete Attribute Data Sets.

Algorithms for Bounded%2DError Correlation of High Dimensional Data in Microarray Experiments.
The problem of clustering continuous valued data has been well studied in literature. Its application to microarray analysis relies on such algorithms as k-means, dimensionality reduction techniques, and graph-based approaches for building dendrograms of sample data. In contrast, similar problems for discrete-attributed data are relatively unexplored. An instance of analysis of discrete-attributed data arises in detecting co-regulated samples in microarrays. In this paper, we present an algorithm and a software framework, PROXIMUS, for error-bounded clustering of highdimensional discrete attributed datasets in the context of extracting co-regulated samples from microarray data. We show that PROXIMUS delivers outstanding performance in extracting accurate patterns of gene-expression.
An Efficient Protocol for Yao%3Fs Millionaires%3F Problem.
The increase in volume and sensitivity of data communicated and processed over the Internet has been accompanied by a corresponding need for e-commerce techniques in which entities can participate in a secure and anonymous fashion. Even simple arithmetic operations over a set of integers partitioned over a network require sophisticated algorithms. As a part of our earlier work, we have developed a secure protocol for computing dot products of two vectors. In this paper,we present a secure protocol for Yao’s millionaires’ problem. In this problem, each of the two participating parties have a number and the objective is to determine whose number is larger without disclosing any information about the numbers. This problem has direct applications in on-line bidding and auctions. Furthermore, combined with a secure dot-product, a solution to this secure multiparty computation provides necessary building blocks for such basic operations as frequent item-set generation in association rule mining. Although an asymptotically optimal solution for the secure multiparty computation of the ‘less-or-equal ’ predicate exists in literature, this protocol is not suited for practical applications. Here, we present a protocol which has a much simpler structure and is more efficient for numbers in ranges practically encountered in typical e-commerce applications. Furthermore, advances in cryptanalysis and the subsequent increase in key lengths for public-key cryptographic systems accentuate the advantage of the proposed protocol. We present experimental evidence demonstrating the efficiency of the proposed protocol both in terms of time and communication overhead. Keywords: secure multiparty computations, Yao’s millionaires’ problem, on-line bidding
Spectral LPM An Optimal Locality%2DPreserving Mapping using the Spectral %28not Fractal%29 Order.
For the past two decades, fractals (e.g., the Hilbert and Peano space-filling curves) have been considered the natural method for providing a locality-preserving mapping. The idea behind a locality-preserving mapping is to map points that are nearby in the multi-dimensional space into points that are nearby in the one-dimensional space. In this paper, we argue against the use of fractals in locality-preserving mapping algorithms, and present examples with experimental evidence to show why fractals produce poor locality-preserving mappings. In addition, we propose an optimal locality-preserving mapping algorithm, termed the Spectral Locality-Preserving Mapping algorithm (Spectral LPM, for short), that makes use of the spectrum of the multi-dimensional space. We give a mathematical proof for the optimality of Spectral LPM, and also demonstrate its practical use.
Adaptive Data Structures for IP Lookups.
The problem of efficient data structures for IP lookups has been well studied in literature. Techniques such as LC tries and Extensible Hashing are commonly used. In this paper, we address the problem of generalizing LC tries and Extensible Hashing, based on traces of past lookups, to provide performance guarantees for memory sub-optimal structures. As a specific example, if a memory-optimal (LC) trie takes 6MB and the total memory at the router is 8MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are b fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have  22 fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of O(#(d)n    log n) and a space complexity of O(n), where n is the number of nodes of the trie and d its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically O(log n).Inthiscase,#(d)=O(log    n). We demonstrate experimentally the performance and scalability of the algorithm on actual routing data. We also show that our algorithm significantly outperforms Extensible Hashing for the same amount of memory.
PROXIMUS a framework for analyzing very high dimensional discrete%2Dattributed datasets.
This paper presents an efficient framework for error-bounded compression of high-dimensional discrete attributed datasets. Such datasets, which frequently arise in a wide variety of applications, pose some of the most significant challenges in data analysis. Subsampling and compression are two key technologies for analyzing these datasets. PROXIMUS provides a technique for reducing large datasets into a much smaller set of representative patterns, on which traditional (expensive) analysis algorithms can be applied with minimal loss of accuracy. We show desirable properties of PROXIMUS in terms of runtime, scalability to large datasets, and performance in terms of capability to represent data in a compact form. We also demonstrate applications of PROXIMUS in association rule mining. In doing so, we establish PROXIMUS as a tool for preprocessing data before applying computationally expensive algorithms or as a tool for directly extracting correlated patterns. Our experimental results show that use of the compressed data for association rule mining provides excellent precision and recall values (near 100%) across a range of support thresholds while reducing the time required for association rule mining drastically.
Multipole%2Dbased preconditioners for large sparse linear systems.

Semi%2Ddiscrete Matrix Transforms %28SDD%29 for Image and Video Compression.
| A wide variety of matrix transforms have been used for compression of image and video data. Transforms have also been used for motion estimation and quantization. One such transform is the singularvalue decomposition (SVD) that relies on low rank approximations of the matrix for computational and storage eciency. In this paper, we describe the use of a variant of SVD in image and video compression. This variant, rst proposed by Peleg and O&#039;Leary [5], called semi-discrete decomposition (SDD) restricts the elements of the outer product vectors to 0/1/-1. Thus approximations of much higher rank can be stored for the same amount of storage. We demonstrate the superiority of SDD over SVD for a variety of compression schemes. We also show that DCT-based compression is still superior to SDD-based compression. However, we demonstrate that SDD facilitates fast and accurate pattern matching and motion estimation; thus presenting excellent opportunities for improved compression.  I. Introducti...
Oceanus A Distributed Web%2DBased Framework for Execution of Genetic Algorithms.

A Secure Protocol for Computing Dot%2DProducts in Clustered and Distributed Environments.
Dot-products form the basis of various applications ranging from scientific computations to commercial applications in data mining and transaction processing. Typical scientific computations utilizing sparse iterative solvers use repeated matrix-vector products. These can be viewed as dot-products of sparse vectors. In database applications, dot-products take the form of counting operations. With widespread use of clustered and distributed platforms, these operations are increasingly being performed across networked hosts. Traditional APIs for messaging are susceptible to sniffing, and the data being transferred between hosts is often enough to compromise the entire computation. For example, in a domain decomposition based sparse solver, the entire solution can often be reconstructed easily from boundary values that are communicated on the net. In yet other applications, dot-products may be performed across two hosts that do not want to disclose their vectors, yet, they need to compute the dot-product. In each of these cases, there is a need for secure and anonymous dotproduct protocols. Due to the large computational requirements of underlying applications, it is highly desirable that secure protocols add minimal overhead to the original algorithm. Finally, by its very nature, dotproducts leak limited amounts of information – one of the parties can detect an entry of the other party’s vector by simply probing it with a vector with a 1 in a particular location and zeros elsewhere. Given all of these constraints, traditional cryptographic protocols are generally unsuitable due to their significant computational and communication overheads. In this paper, we present an extremely efficient and sufficiently secure protocol for computing the dot-product of two vectors using linear
MOBY %2D A Mobile Peer%2Dto%2DPeer Service and Data Network.
This paper describes the design and implementation of MOBY, a network for mobile peer-to-peer exchange of services and data. Constraints on computing power of mobile devices, limited hardware, networking, and software resources, and ad-hoc nature of mobile clients pose considerable challenges from the points of view of supporting performance goals, ease of service integration, and adaptation. These challenges are addressed in MOBY by dynamic service location and client mapping, surrogates for mobile clients, and standardized interfaces built upon off-the-shelf software components. 1. Introduction. The emergence of peer-to-peer (P2P) networks for accessing vast amounts of data and diverse services coupled
Algebraic Techniques for Analysis of Large Discrete%2DValued Datasets.
With the availability of large scale computing platforms and instrumentation  for data gathering, increased emphasis is being placed on efficient  techniques for analyzing large and extremely high-dimensional datasets. In this  paper, we present a novel algebraic technique based on a variant of semi-discrete  matrix decomposition (SDD), which is capable of compressing large discretevalued  datasets in an error bounded fashion. We show that this process of compression  can be thought of as identifying dominant patterns in underlying data.
2D%2Dpattern matching image and video compression theory

Real%2DTime Decompression of Streaming Video Using Mobile Code.

Architecture Independent Analysis of Parallel Programs.

Compression of particle data from hierarchical approximate methods.
This article presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as the Barnes-Hut and Fast Multipole Methods. Due to approximations introduced by hierarchical methods, various parameters (such as position, velocity, acceleration, potential) associated with a particle can be bounded by distortion radii. Using this distortion radii, we develop storage schemes that guarantee error bounds while maximizing compression. Our schemes make extensive use of spatial and temporal coherence of particle behavior and yield compression ratios higher than 12:1 over raw data, and 6:1 over gzipped (LZ) raw data for selected simulation instances. We demonstrate that for uniform distributions with 2M particles, storage requirements can be reduced from 24 MB to about 1.8 MB (about 7 bits per particle per timestep) for storing particle positions. This is significant because it enables faster storage/retrieval, better temporal resolution, and improved analysis. Our results are shown to scale from small systems (2K particles) to much larger systems (over 2M particles). The associated...
Mining scientific data.
this article, we give an
When being Weak is Brave Privacy in Recommender Systems

Privacy Risks in Recommender Systems.
this article, we can state some general guidelines. Like most problems in computer security, the ideal deterrents are better awareness of the issues and more openness in how systems operate in the marketplace. In particular, individual sites should clearly state the policies and methodologies they employ with recommender systems, including the role played by straddlers in their data sets and system designs. This is especially true for sites with multiple homogeneous networks (as in Figures 6c and 6d).   By conveying benefits and risks to users intuitively, recommender systems could achieve greater acceptance. We envisage three general ways to highlight the implications of our analyses. # Present plots of benefit and risk versus usermodifiable parameters such as ratings, w, and l (if the algorithm allows their direct specification) to allow users to make informed choices about their levels of involvement
Summary Structures for Frequency Queries on Large Transaction Sets.
As large-scale databases become commonplace, there has been significant  interest in mining them for commercial purposes. One of the basic tasks that  underlies many of these mining operations is querying of transaction sets for  frequencies of specified attribute values. The size of these databases makes it  important to develop summary structures capable of high compression ratios  as well as supporting fast frequency queries. The nature of the problem and  its differences with respect to traditional text compression allows very high  compression ratios.  In this paper, we propose a binary trie-based summary structure for representing  transaction sets. We demonstrate that this trie structure, when augmented  with an appropriate set of horizontal pointers, can support frequency  queries several orders of magnitude faster than raw transaction data. We improve  the memory characteristics of our scheme by compressing the trie into  a Patricia trie and demonstrate that this does not have...
2D%2DPattern Matching Image and Video Compression.
In this paper, we present a lossy data compression scheme based on an approximate two  dimensional pattern matching (2D-PMIC) extension of the Lempel-Ziv lossless scheme. We  apply the scheme to image and video compression and report on our theoretical and experimental  results. Theoretically, we show that the so called fixed database model leads to suboptimal  compression. Furthermore, the compression ratio of this model is as low as the generalized  entropy that we define in the paper. We use this model for our video compression scheme  and present experimental results. For image compression we use a growing database model for  which we provide an approximate analysis (which will be presented in the final version of the  paper). The implementation of 2D-PMIC is a challenging problem from the algorithmic point  of view. We use a range of novel techniques and data structures such as k-d trees, generalized  run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion  level to achieve good compression ratios at high compression speeds. We demonstrate bit rates  in the range of 0:25 \Gamma 0:5 bpp for high quality images and data rates in the range of 0:15 \Gamma 0:4  Mbps for video compression.
Data Mining From Serendipity to Science %2D Guest Editors%27 Introduction.

State of the Art in Parallel Search Techniques for Discrete Optimization Problems.

Scalable Parallel Formulations of the Barnes%2DHut Method for n%2DBody Simulations.
In this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.   
Role of Message%2DPassing in Performance Oriented Parallel Programming.

N%2DBody Simulations Using Message Passsing Parallel Computers.

Parallel Matrix%2DVector Product Using Approximate Hierarchical Methods.
Matrix-vector products (mat-vecs) form the core of iterative methods used for solving dense linear systems. Often, these systems arise in the solution of integral equations used in electromagnetics, heat transfer, and wave propagation. In this paper, we present a parallel approximate method for computing mat-vecs used in the solution of integral equations. We use this method to compute dense mat-vecs of hundreds of thousands of elements. The combined speedups obtained from the use of approximate methods and parallel processing represent an improvement of several orders of magnitude over exact mat-vecs on uniprocessors. We demonstrate that our parallel formulation incurs minimal parallel processing overhead and scales up to a large number of processors. We study the impact of varying the accuracy of the approximate mat-vec on overall time and on parallel efficiency.    This work was supported by IST/BMDO through Army Research Office contract DA/DAAH04-93-G-0080, NSF grant NSG/1RI-921694...
Parallel Search Algorithms for Discrete Optimization Problems.

Introduction to Parallel Computing.

Scalable parallel formulations of the Barnes%2DHut method for n%2Dbody simulations.
In this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.   
Scalable Load Balancing Techniques for Parallel Computers.
In this paper we analyze the scalability of a number of load balancing algorithms which can  be applied to problems that have the following characteristics : the work done by a processor  can be partitioned into independent work pieces; the work pieces are of highly variable sizes;  and it is not possible (or very difficult) to estimate the size of total work at a given processor.  Such problems require a load balancing scheme that distributes the work dynamically among  different processors.  Our goal here is to determine the most scalable load balancing schemes for different architectures  such as hypercube, mesh and network of workstations. For each of these architectures,  we establish lower bounds on the scalability of any possible load balancing scheme. We present  the scalability analysis of a number of load balancing schemes that have not been analyzed  before. This gives us valuable insights into their relative performance for different problem and  architectural characteristi...
Scalability Analysis of Partitioning Strategies for Finite Element Graphs A Summary of Results.

